import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/*
串联所有单词的字串
不亏是困难题，就是比一般的复杂很多
借助了上一个题的思路，这个题就简单很多
也是采用滑动窗口和哈希表的方法

 */
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        Map<String,Integer> map=new HashMap<>();
        List<Integer> list=new ArrayList<>();

        for (int i = 0; i < words.length; i++) {
            map.put(words[i],map.getOrDefault(words[i],0)+1);
        }

        for (int i = 0; i < words[0].length(); i++) {
            //可能有不同的位置
            Map<String,Integer> map1=new HashMap<>();
            //开始一种情况
            for (int left=i,right=i,count=0;right+words[0].length()<=s.length(); right+=words[0].length()) {
                String tem=s.substring(right,right+words[0].length());
                //入窗口
                map1.put(tem,map1.getOrDefault(tem,0)+1);
                //更新状态
                if(map1.get(tem)<=map.getOrDefault(tem,0)){
                    count++;
                }
                //判断
                if(right-left+1>words[0].length()* words.length){
                    String tL=s.substring(left,left+words[0].length());
                    //更新状态，这个要先执行
                    //如果已经出窗口了就会影响哈希表的大小
                    if(map1.get(tL)<=map.getOrDefault(tL,0)){
                        count--;
                    }
                    //出窗口
                    map1.put(tL,map1.getOrDefault(tL,0)-1);
                    left+=words[0].length();
                }
                //更新结果
                if(count== words.length){
                    list.add(left);
                }
            }
        }

        return list;
    }
}